#pragma once
#include "common.h"

template <typename T>
class FIFO
{
private:
    size_t m_max_size;
    std::vector<T> m_storage;
    std::vector<bool> valid;
    size_t m_size;
    int wptr, rptr, max_ptr;

public:
    int begin()
    {
        return rptr;
    }
    int end()
    {
        return wptr;
    }

    T &operator[](int index)
    {
        assert(valid[index]);
        return m_storage[index];
    }

    FIFO() : FIFO(16)
    {
    }
    FIFO(size_t max_size)
    {
        resize(max_size);
    }
    void resize(size_t max_size)
    {
        m_max_size = max_size;
        max_ptr = static_cast<int>(max_size);
        m_storage.resize(m_max_size);
        valid.resize(max_size);

        clear();
    }
    int push(T t)
    {
        assert(!full());
        int index = wptr;
        assert(!valid[wptr]);
        m_storage[wptr] = t;
        valid[wptr] = true;
        wptr++;
        if (wptr >= max_ptr)
        {
            wptr -= max_ptr;
        }
        m_size++;
        return index;
    }
    void pop()
    {
        assert(!empty());
        assert(valid[rptr]);
        valid[rptr] = false;
        rptr++;
        if (rptr >= max_ptr)
        {
            rptr -= max_ptr;
        }
        m_size--;
    }
    T &front()
    {
        assert(!empty());
        assert(valid[rptr]);
        return m_storage[rptr];
    }
    void clear()
    {
        wptr = 0;
        rptr = 0;
        m_size = 0;
        for (size_t i = 0; i < m_max_size; i++)
        {
            valid[i] = false;
        }
    }
    bool full()
    {
        assert(m_size <= m_max_size);
        return m_size == m_max_size;
    }
    bool empty()
    {
        return m_size == 0;
    }
    size_t size()
    {
        return m_size;
    }
    size_t max_size()
    {
        return m_max_size;
    }
};

template <typename T>
class ConstAllocator
{
private:
    size_t m_max_size;
    size_t m_size;

    FIFO<T *> free_list;
    std::vector<T> m_storage;

public:
    ConstAllocator(size_t max_size) { resize(max_size); }

    ConstAllocator() : ConstAllocator(128) {}

    void resize(size_t max_size)
    {
        m_max_size = max_size;
        free_list.resize(max_size);
        m_storage.resize(max_size);
        clear();
    }

    void clear()
    {
        free_list.clear();
        for (size_t i = 0; i < m_max_size; i++)
        {
            free_list.push(&m_storage[i]);
        }
        m_size = 0;
    }

    T *malloc()
    {
        assert(free_list.size() > 0);
        T *t = free_list.front();
        free_list.pop();
        return t;
    }

    void free(T *t)
    {
        assert(((uintptr_t)t - (uintptr_t)&m_storage[0])/sizeof(T) < m_max_size);
        free_list.push(t);
    }
};
#define USE_ConstAllocator 1


template <typename T>
class ConstList
{
public:
    typedef struct _Node
    {
        struct _Node *next;
        struct _Node *prev;
        T data;
    } Node;
private:

    Node *front_node, *back_node;

    size_t m_max_size;
    size_t m_size;
#if USE_ConstAllocator
    ConstAllocator<Node> allocator;
#endif

public:
    ConstList() : ConstList(16)
    {
    }
    ConstList(size_t max_size)
    {
        resize(max_size);
    }

    Node *begin()
    {
        return front_node;
    }
    Node *end()
    {
        return NULL;
    }

    void resize(size_t max_size)
    {
        // SPDLOG_TRACE("[ConstList] resize to {}", max_size);
        m_max_size = max_size;
#if USE_ConstAllocator
        allocator.resize(max_size);
#endif
        clear();
    }
    void clear()
    {
#if USE_ConstAllocator
        allocator.clear();
#endif
        front_node = NULL;
        back_node = NULL;
        m_size = 0;
    }

    T &front()
    {
        assert(!empty());
        // SPDLOG_TRACE("[ConstList] front {}", (uintptr_t)front_node);
        return front_node->data;
    }
    T &back()
    {
        assert(!empty());
        // SPDLOG_TRACE("[ConstList] back {}", (uintptr_t)back_node);
        return back_node->data;
    }
    Node *push_back(T data)
    {
        assert(!full());
        // SPDLOG_TRACE("[ConstList] push_back {}", m_size);
#if USE_ConstAllocator
        Node *node = allocator.malloc();
#else
        Node *node = new Node;
#endif
        node->data = data;
        if (empty())
        {
            front_node = node;
            back_node = node;
            node->prev = NULL;
            node->next = NULL;
        }
        else
        {
            node->prev = back_node;
            node->next = NULL;
            back_node->next = node;
            back_node = node;
        }
        m_size++;
        return node;
    }
    Node *push_front(T data)
    {
        assert(!full());
        // SPDLOG_TRACE("[ConstList] push_front {}", m_size);
#if USE_ConstAllocator
        Node *node = allocator.malloc();
#else
        Node *node = new Node;
#endif
        node->data = data;
        if (empty())
        {
            front_node = node;
            back_node = node;
            node->prev = NULL;
            node->next = NULL;
        }
        else
        {
            node->prev = NULL;
            node->next = front_node;
            front_node->prev = node;
            front_node = node;
        }
        m_size++;
        return node;
    }
    void pop_back()
    {
        assert(!empty());
        // SPDLOG_TRACE("[ConstList] pop_back {}", m_size);
        Node *new_back_node = back_node->prev;
#if USE_ConstAllocator
        allocator.free(back_node);
#else
        delete back_node;
#endif
        back_node = new_back_node;
        if (back_node)
            back_node->next = NULL;
        m_size--;
    }
    void pop_front()
    {
        assert(!empty());
        Node *new_front_node = front_node->next;
        // SPDLOG_TRACE("[ConstList] pop_front {}", m_size);
#if USE_ConstAllocator
        allocator.free(front_node);
#else
        delete front_node;
#endif
        front_node = new_front_node;
        if (front_node)
            front_node->prev = NULL;
        m_size--;
    }

    Node *erase(Node *node)
    {
        assert(node);
        // SPDLOG_TRACE("[ConstList] erase node {}", (uintptr_t)node);
        Node *next = node->next;
        Node *prev = node->prev;
        if (next)
        {
            next->prev = node->prev;
        }
        else
        {
            back_node = prev;
        }
        if (prev)
        {
            prev->next = node->next;
        }
        else
        {
            front_node = next;
        }
#if USE_ConstAllocator
        allocator.free(node);
#else
        delete node;
#endif
        m_size--;
        return next;
    }

    bool full()
    {
        return m_size >= m_max_size;
    }
    bool empty()
    {
        return m_size == 0;
    }
    size_t size()
    {
        return m_size;
    }
};
